class Solution27 {
    public static int count;
    public static int ret;
    public static int[] dx = {1,-1,0,0};
    public static int[] dy = {0,0,1,-1};
    public static int getMaximumGold(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] != 0) {
                    int tmp = grid[i][j];
                    count += grid[i][j];
                    grid[i][j] = 0;
                    dfs(grid,i,j);
                    count -= tmp;
                    grid[i][j] = tmp;
                }
            }
        }
        return ret;
    }

    public static void dfs(int[][] grid,int x,int y) {
        if(ret < count) ret = count;
        for(int k = 0; k < 4; k++) {
            int row = x + dx[k];
            int col = y + dy[k];
            if(row >= 0 && row < grid.length && col >= 0 && col < grid[0].length && grid[row][col] != 0) {
                int tmp = grid[row][col];
                count += grid[row][col];
                grid[row][col] = 0;
                dfs(grid,row,col);
                count -= tmp;
                grid[row][col] = tmp;
            }
        }
    }

    public static void main(String[] args) {
        int[][] ret = {{0,6,0},{5,8,7},{0,9,0}};
        int co = getMaximumGold(ret);
        System.out.println(co);
    }
}